Serialize and deserialize binary tree

Time: O(N); Space: O(H); medium

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example 1:

  1
 / \
2   3
   / \
  4   5

Input: root = {TreeNode} [1,2,3,#,#,4,5]

Output:

  • Serialize: “1 2 # # 3 4 # # 5 # #”

  • Deserialize: {TreeNode} [1,2,3,None,None,4,5]

Explanation:

  • just the same as how LeetCode OJ serializes a binary tree.

You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Notes:

  • Do not use class member/global/static variables to store states.

  • Your serialize and deserialize algorithms should be stateless.

[48]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Auxiliary Tools

[49]:

from graphviz import Graph

class TreeTasks(object):
    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left and tree.left.val != "#":
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right and tree.right.val != "#":
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

Solution

[50]:

class Codec(object):

    def serialize(self, root) -> str:
        '''
        Encodes a tree to a single string
        :type root: TreeNode
        :rtype: str
        '''
        def serializeHelper(node):
            if not node:
                vals.append('#')
            else:
                vals.append(str(node.val))
                serializeHelper(node.left)
                serializeHelper(node.right)
        vals = []
        serializeHelper(root)

        return ' '.join(vals)

    def deserialize(self, data) -> TreeNode:
        '''
        Decodes your encoded data (string) to tree
        :type data: str
        :rtype: TreeNode
        '''
        def deserializeHelper():
            val = next(vals)
            if val == '#':
                return None
            else:
                node = TreeNode(int(val))
                node.left = deserializeHelper()
                node.right = deserializeHelper()
                return node

        def isplit(source, sep):
            sepsize = len(sep)
            start = 0
            while True:
                idx = source.find(sep, start)
                if idx == -1:
                    yield source[start:]
                    return

                yield source[start:idx]

                start = idx + sepsize

        vals = iter(isplit(data, ' '))

        return deserializeHelper()

[51]:

codec = Codec()

# [1,2,3,#,#,4,5]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)

# 1. Serialize
s = codec.serialize(root)
assert s == "1 2 # # 3 4 # # 5 # #"

# 2. Deserialize
tree = codec.deserialize(s)
t = TreeTasks()
dot = t.visualize_tree(tree)

assert tree.val == 1
assert tree.left.val == 2
assert tree.right.val == 3
assert tree.right.left.val == 4
assert tree.right.right.val == 5
../../_images/topics_tree_0297_serialize_and_deserialize_binary_tree_[O(N),O(H),hard]_6_0.svg